package sword.chapter11BinarySearch;

/**
 * 排序数组中只出现一次的数字
 *
 * 二分查找组，每两个数为一组
 * 1. 每两个数分一组，数组一定是奇数，n个数就有 n/2 + 1 组，9个数就有5组
 * 2. left=0 right= length/2，下标代表第index+1组，mid是中间组，在nums中的下标i就是mid*2
 *
 * 判断当前组数值是否相同，相同则在后面的组中 left = mid +1
 * 不同，当前下标的前两个数是否相同。相同则说明当前组是第一个值不同的组，返回组内第一个数（结果值）；不同则结果值在前面的组 right = mid -1；
 * 最后都还没有找到，则最后一个数是结果值
 *
 * @author K
 * @date 2021/12/23 08:54
 */
public class S70SingleNonDuplicate {

    public static int s70A(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result = result ^ num;
        }

        return result;
    }

    public static int s70(int[] nums) {
        int left = 0;
        int right = nums.length / 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            int i = mid * 2;
            if (i < nums.length - 1 && nums[i] != nums[i + 1]) {
                if (mid == 0 || nums[i - 2] == nums[i - 1]) {
                    return nums[i];
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        int result = s70(nums);
        int result1 = s70A(nums);
        System.out.println();
    }
}
